Tries are tree data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. A trie data structure turns a string set into a digital search tree. Several operations may be supported using the data structure, such as mapping the strings to integers, retrieving a string from the trie, performing prefix searches and many others. Thanks to their simplicity and functionality tries may be used in a variety of fields including but not limited to computational biology, data compression, data mining, information retrieval, natural language processing, network routing, pattern matching, text processing and web applications.
A path-decomposed trie is a trie (tree data structure for storing a set of strings) where each node in the path decomposed trie represents a path in the trie. A path-decomposed trie is thus smaller than a trie from which it is formed and this reduces space requirements. Reducing space requirements is increasingly important, for example, for web-scale applications such as internet search engines and others. However, a trade-off may occur between reducing space requirements and reducing running time of the data structures during use for operations such as mapping the strings to integers, retrieving a string from the trie and other queries.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known path-decomposed trie data structures.